//momenta 面试题
//前面数组升序，后面数组降序，找到最大值；
//降序数组中找到目标值；
//https://leetcode.cn/problems/find-in-mountain-array/
//lower_bound与 binary_search 深度使用

#include <vector>
#include <iostream>

using namespace std;

int findMax(const std::vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2; // 防止溢出

        if (arr[mid] < arr[mid + 1]) {
            // 如果中间值小于其右侧的值，说明最大值在右侧
            left = mid + 1;
        } else {
            // 否则，最大值在左侧或就是中间值
            right = mid;
        }
    }

    // 当 left == right 时，找到最大值
    std::cout << "index:" << left << ",value:" << arr[left] << std::endl;
    return arr[left];
}


int binarySearch(vector<int>& data, int left,int right,int k){
    // 左右边界
    int l = left, r = right;
    while(l < r){
        // 二分求中点
        int m = l+(r-l)/2;
        if(data[m] == k){
            l=m;
            return l;
        }else if(data[m]>k){
            l=m+1;
        }else {
            r=m;
        }
    }
    // 返回左边界
    return -1;
}



class Solution {
public:
    int findMax(const std::vector<int>& arr) {
        int left = 0;
        int right = arr.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2; // 防止溢出
            if (arr[mid] < arr[mid + 1]) {
                // 如果中间值小于其右侧的值，说明最大值在右侧
                left = mid + 1;
            } else {
                // 否则，最大值在左侧或就是中间值
                right = mid;
            }
        }
        return left;
    }


    int findInMountainArray(int target, MountainArray &mountainArr) {

        std::vector<int> vec1{};
        int i=0;
        while(i<mountainArr.length()){
            vec1.emplace_back(mountainArr.get(i));
            ++i;
        }
        int max_loc = findMax(vec1);
        auto res1= std::lower_bound(vec1.begin(),vec1.begin()+max_loc+1,target);
        if (res1 != vec1.begin()+max_loc+1() && *res1 == target) {
            return res1- vec1.begin();
        }
        auto res2 = std::lower_bound(vec1.begin()+max_loc+1, vec1.end(), target, std::greater<int>());
         if (res2 != vec1.end() && *res2 == target) {
            return res2- vec1.begin();
        }
        return -1;
    }
};